20220409-TIL

오늘 알고리즘 문제는 발상의 전환의 필요한 배낭 문제였다. (배낭 문제.. 쉽지 않다..)

• 앱 문제는 특정 비용에 대한 최대 메모리 공간을 테이블에 기록하는 식으로 풀었다.
• 처음에는, 우선순위 큐를 사용하는 풀이를 생각했는데, 반례가 생각나서 배제했다..
  (작은 비용부터 확인하면서 메모리 공간을 계산했을 때, 최선의 선택을 할 수 없는 경우)
• 백트래킹 형태로도 풀어봤는데 n = 100일 때에 시간이 너무 오래 걸려서 배제했다;
• 질문 게시판에도 괜찮은 글이 없어서, 또 검색해서 풀었다.. (동적계획법.. ㅂㄷㅂㄷ)
  (그마저도 테이블 형태만 보고 풀어보려다가, 점화식 구성에서 막혀서 제대로 못 품 ㅜㅠ)